package org.apache.commons.graph.algorithms.visit

import org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph
import org.apache.commons.graph.CommonsGraph.visit
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledEdge
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.UndirectedMutableGraph
import org.junit.Assert
import org.junit.Test

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

class VisitTestCase {
    @Test(expected = IllegalStateException::class)
    fun testNotExistVertex() {
        val input: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                }
            })

        visit(input).from(BaseLabeledVertex("NOT EXIST"))
    }

    /**
     * Graph picture can be see
     * [here](http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm)
     */
    @Test
    fun testVerifyBreadthFirstSearch() {
        // input graph

        val input: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    val r = addVertex(BaseLabeledVertex("r"))
                    val s = addVertex(BaseLabeledVertex("s"))
                    val t = addVertex(BaseLabeledVertex("t"))
                    val u = addVertex(BaseLabeledVertex("u"))
                    val v = addVertex(BaseLabeledVertex("v"))
                    val w = addVertex(BaseLabeledVertex("w"))
                    val x = addVertex(BaseLabeledVertex("x"))
                    val y = addVertex(BaseLabeledVertex("y"))

                    addEdge(BaseLabeledEdge("s <-> r")).from(s).to(r)
                    addEdge(BaseLabeledEdge("s <-> w")).from(s).to(w)

                    addEdge(BaseLabeledEdge("r <-> v")).from(r).to(v)

                    addEdge(BaseLabeledEdge("w <-> t")).from(w).to(t)
                    addEdge(BaseLabeledEdge("w <-> x")).from(w).to(x)

                    addEdge(BaseLabeledEdge("t <-> u")).from(t).to(u)
                    addEdge(BaseLabeledEdge("t <-> x")).from(t).to(x)

                    addEdge(BaseLabeledEdge("y <-> u")).from(y).to(u)
                    addEdge(BaseLabeledEdge("x <-> y")).from(x).to(y)
                }
            })

        // expected graph
        val expected: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    val r = addVertex(BaseLabeledVertex("r"))
                    val s = addVertex(BaseLabeledVertex("s"))
                    val t = addVertex(BaseLabeledVertex("t"))
                    val u = addVertex(BaseLabeledVertex("u"))
                    val v = addVertex(BaseLabeledVertex("v"))
                    val w = addVertex(BaseLabeledVertex("w"))
                    val x = addVertex(BaseLabeledVertex("x"))
                    val y = addVertex(BaseLabeledVertex("y"))

                    addEdge(BaseLabeledEdge("s <-> r")).from(s).to(r)
                    addEdge(BaseLabeledEdge("s <-> w")).from(s).to(w)

                    addEdge(BaseLabeledEdge("r <-> v")).from(r).to(v)

                    addEdge(BaseLabeledEdge("w <-> t")).from(w).to(t)
                    addEdge(BaseLabeledEdge("w <-> x")).from(w).to(x)

                    addEdge(BaseLabeledEdge("t <-> u")).from(t).to(u)

                    addEdge(BaseLabeledEdge("x <-> y")).from(x).to(y)
                }
            })

        // actual graph
        val actual = visit(input).from(BaseLabeledVertex("s")).applyingBreadthFirstSearch()

        // assertion
        Assert.assertEquals(expected, actual)
    }

    /**
     * Graph picture can be see
     * [here](http://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/)
     */
    @Test
    fun testVerifyDepthFirstSearch() {
        // expected node set
        val expected: MutableList<BaseLabeledVertex> = ArrayList()

        // input graph
        val input: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    val a = addVertex(BaseLabeledVertex("A"))
                    val b = addVertex(BaseLabeledVertex("B"))
                    val c = addVertex(BaseLabeledVertex("C"))
                    val d = addVertex(BaseLabeledVertex("D"))
                    val e = addVertex(BaseLabeledVertex("E"))
                    val f = addVertex(BaseLabeledVertex("F"))
                    val g = addVertex(BaseLabeledVertex("G"))
                    val h = addVertex(BaseLabeledVertex("H"))
                    val s = addVertex(BaseLabeledVertex("S"))

                    addEdge(BaseLabeledEdge("S <-> A")).from(s).to(a)
                    addEdge(BaseLabeledEdge("S <-> B")).from(s).to(b)

                    addEdge(BaseLabeledEdge("A <-> C")).from(a).to(c)
                    addEdge(BaseLabeledEdge("A <-> D")).from(a).to(d)

                    addEdge(BaseLabeledEdge("B <-> E")).from(b).to(e)
                    addEdge(BaseLabeledEdge("B <-> F")).from(b).to(f)

                    addEdge(BaseLabeledEdge("E <-> H")).from(e).to(h)
                    addEdge(BaseLabeledEdge("E <-> G")).from(e).to(g)

                    // populate the expected list, order is not the same in the pic, due to Stack use
                    expected.add(s)
                    expected.add(b)
                    expected.add(f)
                    expected.add(e)
                    expected.add(g)
                    expected.add(h)
                    expected.add(a)
                    expected.add(d)
                    expected.add(c)
                }
            })

        // actual node set
        val actual = visit(input).from(BaseLabeledVertex("S")).applyingDepthFirstSearch(org.apache.commons.graph.algorithms.visit.NodeSequenceVisitor())

        // assertion
        Assert.assertEquals(expected, actual)
    }
}
